<!DOCTYPE html>
<html lang="en">

<head>
	<meta charset="UTF-8">
	<meta name="viewport" content="width=device-width, initial-scale=1.0">
	<title>2462. 雇佣 K 位工人的总代价</title>
</head>

<body>
  https://leetcode.cn/problems/total-cost-to-hire-k-workers/description/?envType=daily-question&envId=2024-05-01
</body>

<script>

class MinHeap {
    constructor(list = []) {
      this.heap = list
      return this.sort()
    }

    insert(val) {
      this.heap.push(val);
      return this.sort()
    }

    sort() {
      this.heap.sort((a, b) => a - b)
      return this
    }

    pop() {
      return this.heap.pop()
    }

    getMin() {
      return this.heap.shift()
    }

    viewMin() {
      return this.heap[0]
    }
  }
  /**
   * @param {number[]} costs
   * @param {number} k
   * @param {number} candidates
   * @return {number}
   */
  var totalCost = function (costs, k, candidates) {

    let total = 0;

    let findIndex = null;

    let endList = null;
    let startList = null

    if (costs.length > candidates * 2) {
      endList = new MinHeap(costs.splice(costs.length - candidates, costs.length));
      startList = new MinHeap(costs.splice(0, candidates));
    }

    for (i = 0; i < k; i++) {
      // debugger
      if (endList && startList) {
        let startMin = startList.viewMin();
        let endMin = endList.viewMin();

        if (startMin <= endMin) {
          findVal = startList.getMin();
          if (costs && costs.length) startList.insert(costs.shift())
        } else {
          findVal = endList.getMin();
          if (costs && costs.length) endList.insert(costs.pop())
        }

        if (!costs.length) {
          costs = [...startList.heap, ...endList.heap];
          startList = null;
          endList = null;
        }
      } else {
        if (costs.length === 0) return total;
        findIndex = costs.indexOf(Math.min(...costs));
        findVal = costs.splice(findIndex, 1)[0];
      }

      total += findVal;
    }

    return total;
  };

  // let res = totalCost([17, 12, 10, 2, 7, 2, 11, 20, 8], 3, 4);
  // let res = totalCost([2, 2, 2, 2, 1, 2, 2, 2, 2], 9, 2);
  // let res = totalCost([31, 25, 72, 79, 74, 65, 84, 91, 18, 59, 27, 9, 81, 33, 17, 58], 11, 2);

  let res = totalCost([28, 35, 21, 13, 21, 72, 35, 52, 74, 92, 25, 65, 77, 1, 73, 32, 43, 68, 8, 100, 84, 80, 14, 88, 42, 53, 98, 69, 64, 40, 60, 23, 99, 83, 5, 21, 76, 34]
    , 7, 12);
  console.log(res)
</script>

</html>
